/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-12-11
 * Time:22:11
 */

import java.util.ArrayList;
import java.util.List;

/**
 * LCR 080. 组合
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 * 示例 1:
 * 输入: n = 4, k = 2
 * 输出:
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 */
public class combine {
    public static void main(String[] args) {
        combine(4,2);
    }
    static List<List<Integer>> ret;
    static List<Integer> path;
    static int n;
    static int k;
    public static List<List<Integer>> combine(int _n, int _k) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        n = _n;
        k = _k;
        dfs(0);

        return ret;
    }
    // 这里的 start 就是用来剪枝的
    private static void dfs(int start) {
        if (path.size() == k){
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n; i++) {
            path.add(i);
            dfs(i + 1);
            path.remove(path.size() - 1);// 恢复现场
        }
    }
}
